package src.com.java.dtgh.threeDay;

import java.util.Arrays;

public class demo1 {

    public boolean canPartition(int[] nums){

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if(sum % 2 != 0) return false;

        int target = sum >> 1;
        int[] dp = new int[target + 1];
        Arrays.fill(dp, 0);

        int len = nums.length;

        for(int i = 0;i < len;i++){
            for(int j = target;j >= nums[i];j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target] == target;
    }

}
